package com.leetcode.dynamic_programming.bag;

import java.util.Scanner;

/**
 * @author Dennis Li
 * @date 2020/10/13 22:28
 */
public class CompleteBag {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), v = scanner.nextInt();
        int[][] items = new int[n][2];
        int[] dp = new int[v + 1];

        for (int i = 0; i < n; i++) {
            items[i][0] = scanner.nextInt();
            items[i][1] = scanner.nextInt();
        }

        for (int i = 1; i <= n; i++) {
            int[] item = items[i];
            for (int j = item[0]; j <= v; j++) {
                // 从小到大的时候，之前已经包含了k个第i个物品
                dp[j] = Math.max(dp[j], dp[j - item[0]] + item[1]);
            }
        }
    }

    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), v = scanner.nextInt();
        int[] dp = new int[v + 1];

        for (int i = 1; i <= n; i++) {
            int volume = scanner.nextInt(), weight = scanner.nextInt();
            for (int j = weight; j <= v; j++) {
                dp[j] = Math.max(dp[j], dp[j - volume] + weight);
            }
        }
        System.out.println(dp[v]);
    }

}
